package _32_把数组排成最小的数;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * 题目描述
 * 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 * 例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
 */
public class Solution {
    //全排列
    public String PrintMinNumber(int[] numbers) {
        if(numbers.length==0){return "";}
        String[] res= new String[1];
        huisu(0, res, numbers);
        return res[0];
    }

    void huisu(int begin, String[] res, int[] numbers) {
        if (begin == numbers.length-1) {
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<numbers.length;i++){
                sb.append(numbers[i]);
            }
            if(res[0] ==null){
                res[0]=sb.toString();
            }else {
                if(res[0].compareTo(sb.toString())>0){
                    res[0] = sb.toString();
                }
            }
            return;
        }
        for(int i=begin;i<numbers.length;i++){
            swap(numbers,begin,i);
            huisu(begin+1,res,numbers);
            swap(numbers,begin,i);
        }

    }
    void swap(int nums[],int j,int i){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] =tmp;
    }

    /**
     *
     * 第二种方法，对数组进行排列按照 nums[i] +""+nums[j]<nums[j]+""+nums[i]排列
     */
    public String PrintMinNumber2(int[] numbers) {
        if(numbers.length==0){
            return"";
        }
        List<Integer> list = new LinkedList<>();
        for(int i=0;i<numbers.length;i++){
            list.add(numbers[i]);
        }
        list.sort(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return (o1+""+o2).compareTo(o2+""+o1);
            }
        });
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<list.size();i++){
            sb.append(list.get(i));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {3,32,321};
        solution.PrintMinNumber(nums);
    }
}
